1
2
3
4
5
6
7 package io.vavr.collection;
8
9 import io.vavr.Tuple;
10 import org.junit.Test;
11
12 import java.math.BigDecimal;
13 import java.util.*;
14 import java.util.function.Function;
15 import java.util.function.Supplier;
16 import java.util.stream.Collector;
17
18 import static java.util.Comparator.comparingInt;
19 import static java.util.stream.Collectors.toList;
20 import static io.vavr.TestComparators.toStringComparator;
21
22 public class PriorityQueueTest extends AbstractTraversableTest {
23 private final io.vavr.collection.List<Integer> values = io.vavr.collection.List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, 4, 1, 9, 7, 1, 6, 9, 3, 9, 9, 3, 7, 5, 1, 0);
24
25 @Override
26 protected <T> Collector<T, ArrayList<T>, PriorityQueue<T>> collector() {
27 return PriorityQueue.collector();
28 }
29
30 @Override
31 protected <T> PriorityQueue<T> empty() {
32 return PriorityQueue.empty(Comparators.naturalComparator());
33 }
34
35 @Override
36 protected <T> PriorityQueue<T> of(T element) {
37 return PriorityQueue.ofAll(Comparators.naturalComparator(), io.vavr.collection.List.of(element));
38 }
39
40 @Override
41 @SuppressWarnings("unchecked")
42 protected final <T> PriorityQueue<T> of(T... elements) {
43 return PriorityQueue.ofAll(Comparators.naturalComparator(), io.vavr.collection.List.of(elements));
44 }
45
46 @Override
47 protected <T> PriorityQueue<T> ofAll(Iterable<? extends T> elements) {
48 return PriorityQueue.ofAll(Comparators.naturalComparator(), elements);
49 }
50
51 @Override
52 protected <T extends Comparable<? super T>> Traversable<T> ofJavaStream(java.util.stream.Stream<? extends T> javaStream) {
53 return PriorityQueue.ofAll(Comparators.naturalComparator(), javaStream);
54 }
55
56 @Override
57 protected PriorityQueue<Boolean> ofAll(boolean... elements) {
58 return PriorityQueue.ofAll(io.vavr.collection.List.ofAll(elements));
59 }
60
61 @Override
62 protected PriorityQueue<Byte> ofAll(byte... elements) {
63 return PriorityQueue.ofAll(io.vavr.collection.List.ofAll(elements));
64 }
65
66 @Override
67 protected PriorityQueue<Character> ofAll(char... elements) {
68 return PriorityQueue.ofAll(io.vavr.collection.List.ofAll(elements));
69 }
70
71 @Override
72 protected PriorityQueue<Double> ofAll(double... elements) {
73 return PriorityQueue.ofAll(io.vavr.collection.List.ofAll(elements));
74 }
75
76 @Override
77 protected PriorityQueue<Float> ofAll(float... elements) {
78 return PriorityQueue.ofAll(io.vavr.collection.List.ofAll(elements));
79 }
80
81 @Override
82 protected PriorityQueue<Integer> ofAll(int... elements) {
83 return PriorityQueue.ofAll(io.vavr.collection.List.ofAll(elements));
84 }
85
86 @Override
87 protected PriorityQueue<Long> ofAll(long... elements) {
88 return PriorityQueue.ofAll(io.vavr.collection.List.ofAll(elements));
89 }
90
91 @Override
92 protected PriorityQueue<Short> ofAll(short... elements) {
93 return PriorityQueue.ofAll(io.vavr.collection.List.ofAll(elements));
94 }
95
96 @Override
97 protected <T> PriorityQueue<T> tabulate(int n, Function<? super Integer, ? extends T> f) {
98 return PriorityQueue.tabulate(n, f);
99 }
100
101 @Override
102 protected <T> PriorityQueue<T> fill(int n, Supplier<? extends T> s) {
103 return PriorityQueue.fill(n, s);
104 }
105
106 @Override
107 protected boolean useIsEqualToInsteadOfIsSameAs() {
108 return true;
109 }
110
111 @Override
112 protected int getPeekNonNilPerformingAnAction() {
113 return 1;
114 }
115
116 @Override
117 protected boolean emptyShouldBeSingleton() {
118 return false;
119 }
120
121 private static Comparator<Integer> composedComparator() {
122 final Comparator<Integer> bitCountComparator = comparingInt(Integer::bitCount);
123 return bitCountComparator.thenComparing(Comparators.naturalComparator());
124 }
125
126 @Test
127 @Override
128 public void shouldScanLeftWithNonComparable() {
129
130 }
131
132 @Test
133 @Override
134 public void shouldScanRightWithNonComparable() {
135
136 }
137
138 @Override
139 public void shouldPreserveSingletonInstanceOnDeserialization() {
140
141 }
142
143 @Test
144 public void shouldScanWithNonComparable() {
145
146 }
147
148 @Test
149 public void shouldCreateFromStream() {
150 final PriorityQueue<Integer> source = PriorityQueue.ofAll(values.toJavaStream());
151 assertThat(source).isEqualTo(ofAll(values));
152 }
153
154 @Test
155 public void shouldReturnOrdered() {
156 final PriorityQueue<Integer> source = of(3, 1, 4);
157 assertThat(source.isOrdered()).isTrue();
158 }
159
160
161
162 @Test
163 public void shouldNarrowPriorityQueue() {
164 final PriorityQueue<Double> doubles = PriorityQueue.of(toStringComparator(), 1.0d);
165 final PriorityQueue<Number> numbers = PriorityQueue.narrow(doubles);
166 final int actual = numbers.enqueue(new BigDecimal("2.0")).sum().intValue();
167 assertThat(actual).isEqualTo(3);
168 }
169
170
171
172 @Test
173 public void toListIsSortedAccordingToComparator() {
174 final Comparator<Integer> comparator = composedComparator();
175 final PriorityQueue<Integer> queue = PriorityQueue.ofAll(comparator, values);
176 assertThat(queue.toList()).isEqualTo(values.sorted(comparator));
177 }
178
179
180
181 @Test
182 public void shouldMergeTwoPriorityQueues() {
183 final PriorityQueue<Integer> source = of(3, 1, 4, 1, 5);
184 final PriorityQueue<Integer> target = of(9, 2, 6, 5, 3);
185 assertThat(source.merge(target)).isEqualTo(of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3));
186 assertThat(PriorityQueue.of(3).merge(PriorityQueue.of(1))).isEqualTo(of(3, 1));
187 }
188
189
190
191 @Test
192 public void shouldComputeDistinctOfNonEmptyTraversableUsingKeyExtractor() {
193 final Comparator<String> comparator = comparingInt(o -> o.charAt(1));
194 assertThat(PriorityQueue.of(comparator, "5c", "1a", "3a", "1a", "2a", "4b", "3b").distinct().map(s -> s.substring(1))).isEqualTo(of("a", "b", "c"));
195 }
196
197
198
199 @Test
200 public void shouldRemoveAllElements() {
201 assertThat(of(3, 1, 4, 1, 5, 9, 2, 6).removeAll(of(1, 9, 1, 2))).isEqualTo(of(3, 4, 5, 6));
202 }
203
204
205
206 @Test
207 public void shouldEnqueueAllElements() {
208 assertThat(of(3, 1, 4).enqueueAll(of(1, 5, 9, 2))).isEqualTo(of(3, 1, 4, 1, 5, 9, 2));
209 }
210
211
212
213 @Test(expected = NoSuchElementException.class)
214 public void shouldFailPeekOfEmpty() {
215 empty().peek();
216 }
217
218
219
220 @Test
221 public void shouldDeque() {
222 assertThat(of(3, 1, 4, 1, 5).dequeue()).isEqualTo(Tuple.of(1, of(3, 4, 1, 5)));
223 }
224
225 @Test(expected = NoSuchElementException.class)
226 public void shouldFailDequeueOfEmpty() {
227 empty().dequeue();
228 }
229
230
231
232 @Test
233 public void shouldKeepInstanceOfPriorityQueue() {
234 final PriorityQueue<Integer> queue = PriorityQueue.of(1, 3, 2);
235 assertThat(queue.toPriorityQueue()).isSameAs(queue);
236 }
237
238
239
240 @Test
241 public void shouldBehaveExactlyLikeAnotherPriorityQueue() {
242 for (int i = 0; i < 10; i++) {
243 final Random random = getRandom(-1);
244
245 final java.util.PriorityQueue<Integer> mutablePriorityQueue = new java.util.PriorityQueue<>();
246 PriorityQueue<Integer> functionalPriorityQueue = PriorityQueue.empty();
247
248 final int size = 100_000;
249 for (int j = 0; j < size; j++) {
250
251 if (random.nextInt() % 3 == 0) {
252 assertMinimumsAreEqual(mutablePriorityQueue, functionalPriorityQueue);
253
254 final int value = random.nextInt(size) - (size / 2);
255 mutablePriorityQueue.add(value);
256 functionalPriorityQueue = functionalPriorityQueue.enqueue(value);
257 }
258
259 assertMinimumsAreEqual(mutablePriorityQueue, functionalPriorityQueue);
260
261
262 if (random.nextInt() % 5 == 0) {
263 if (!mutablePriorityQueue.isEmpty()) { mutablePriorityQueue.poll(); }
264 if (!functionalPriorityQueue.isEmpty()) {
265 functionalPriorityQueue = functionalPriorityQueue.tail();
266 }
267
268 assertMinimumsAreEqual(mutablePriorityQueue, functionalPriorityQueue);
269 }
270 }
271
272 final Collection<Integer> oldValues = mutablePriorityQueue.stream().sorted().collect(toList());
273 final Collection<Integer> newValues = functionalPriorityQueue.toJavaList();
274 assertThat(oldValues).isEqualTo(newValues);
275 }
276 }
277
278
279
280 @Test
281 public void shouldHaveSortedSpliterator() {
282 assertThat(of(1, 2, 3).spliterator().hasCharacteristics(Spliterator.SORTED)).isTrue();
283 }
284
285 @Test
286 public void shouldHaveOrderedSpliterator() {
287 assertThat(of(1, 2, 3).spliterator().hasCharacteristics(Spliterator.ORDERED)).isTrue();
288 }
289
290 @Test
291 public void shouldHaveSizedSpliterator() {
292 assertThat(of(1, 2, 3).spliterator().hasCharacteristics(Spliterator.SIZED | Spliterator.SUBSIZED)).isTrue();
293 }
294
295 @Test
296 public void shouldNotHaveDistinctSpliterator() {
297 assertThat(of(1, 2, 3).spliterator().hasCharacteristics(Spliterator.DISTINCT)).isFalse();
298 }
299
300 @Test
301 public void shouldReturnSizeWhenSpliterator() {
302 assertThat(of(1, 2, 3).spliterator().getExactSizeIfKnown()).isEqualTo(3);
303 }
304
305
306
307 @Test
308 public void shouldReturnFalseWhenIsSequentialCalled() {
309 assertThat(of(1, 2, 3).isSequential()).isFalse();
310 }
311
312 private void assertMinimumsAreEqual(java.util.PriorityQueue<Integer> oldQueue, PriorityQueue<Integer> newQueue) {
313 assertThat(oldQueue.isEmpty()).isEqualTo(newQueue.isEmpty());
314 if (!newQueue.isEmpty()) {
315 assertThat(oldQueue.peek()).isEqualTo(newQueue.head());
316 }
317 }
318 }